package medium.linkedList;

import struct.ListNode;

/**
 * <a href="https://leetcode.cn/problems/add-two-numbers-ii/">445. 两数相加 II</a>
 * 给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
 * 你可以假设除了数字 0 之外，这两个数字都不会以零开头。
 * 示例1：
 *   输入：l1 = [7,2,4,3], l2 = [5,6,4]
 *   输出：[7,8,0,7]
 * 示例2：
 *   输入：l1 = [2,4,3], l2 = [5,6,4]
 *   输出：[8,0,7]
 * 示例3：
 *   输入：l1 = [0], l2 = [0]
 *   输出：[0]
 * 提示：
 *   链表的长度范围为 [1, 100]
 *   0 <= node.val <= 9
 *   输入数据保证链表代表的数字无前导 0
 * @author 刘学松
 * @date 2023-07-03 9:02
 */
public class 两数相加II {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode temp1 = l1, temp2 = l2;
        while (temp1 != null || temp2 != null) {
            if (temp1 == null) {
                l1 = new ListNode(0, l1);
            } else {
                temp1 = temp1.next;
            }
            if (temp2 == null) {
                l2 = new ListNode(0, l2);
            } else {
                temp2 = temp2.next;
            }
        }
        int carry = add(l1, l2);
        if (carry == 1) {
            return new ListNode(1, l1);
        }
        return l1;
    }

    public int add(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return 0;
        }
        int val = add(l1.next, l2.next) + l1.val + l2.val;
        if (val > 9) {
            l1.val = val-10;
            return 1;
        } else {
            l1.val = val;
            return 0;
        }
    }
}
